import java.util.*;

public class BinaryTree {
    public int x = 0;
    public TreeNode createdTree(){
        TreeNode A = new TreeNode("A");
        TreeNode B = new TreeNode("B");
        TreeNode C = new TreeNode("C");
        TreeNode D = new TreeNode("D");
        TreeNode E = new TreeNode("E");
        TreeNode F = new TreeNode("F");
        TreeNode G = new TreeNode("G");
        TreeNode H = new TreeNode("H");

        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;
        D.left = H;

        return A;
    }
    //创建二叉树
    public TreeNode createdTree(String str){
        TreeNode root = null;
        if(!(str.charAt(x)+"").equals(" ")){
            root = new TreeNode(str.charAt(x++)+"");
            root.left = createdTree(str);
            root.right = createdTree(str);
        }else
            x++;
        return root;
    }
    //以前序和中序创建二叉树
    public int rootIndex = 0;
    public TreeNode buildTree1(String[] preorder, String[] inorder) {
        TreeNode root = buildTreeChild1(preorder, inorder,0, preorder.length);
        return root;
    }
    public TreeNode buildTreeChild1(String[] preorder, String[] inorder, int begin, int end){
        if(begin >= end)
            return null;
        TreeNode root = new TreeNode(preorder[rootIndex]);
        int mid = findIndex1(begin, end, inorder, preorder[rootIndex++]);
        root.left = buildTreeChild1(preorder, inorder, begin, mid);
        root.right = buildTreeChild1(preorder, inorder, mid+1, end);
        return root;
    }
    public int findIndex1(int begin, int end, String[] inorder, String val){
        for(int i = begin; i < end; i++){
            if(inorder[i].equals(val))
                return i;
        }
        return -1;
    }
    //以后序和中序创建二叉树
    public int index = 0;
    public TreeNode buildTree2(String[] inorder, String[] postorder) {
        index = inorder.length-1;
        return buildTreeChild2(inorder, postorder, 0, inorder.length);
    }
    public TreeNode buildTreeChild2(String[] inorder, String[] postorder, int begin, int end){
        if(begin >= end)
            return null;
        TreeNode root = new TreeNode(postorder[index]);
        int mid = findIndex2(inorder, postorder[index--], begin, end);
        root.right = buildTreeChild2(inorder, postorder, mid+1, end);
        root.left = buildTreeChild2(inorder, postorder, begin, mid);
        return root;
    }
    public int findIndex2(String[] inorder, String val, int begin, int end){
        for(int i = begin; i < end; i++){
            if(inorder[i].equals(val))
                return i;
        }
        return -1;
    }
    //前序遍历
    public void preOrder(TreeNode root){
        if(root == null)
            return ;
        System.out.print(root.val+" ");
        preOrder(root.left);
        preOrder(root.right);
    }
    //中序遍历
    public void inOrder(TreeNode root){
        if(root == null)
            return ;
        inOrder(root.left);
        System.out.print(root.val+" ");
        inOrder(root.right);
    }
    //后序遍历
    public void postOrder(TreeNode root){
        if(root == null)
            return ;
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val+" ");
    }
    //获取树中结点的个数
    public int getNodeNum(TreeNode root){
        if(root == null)
            return 0;
        return getNodeNum(root.left)+getNodeNum(root.right)+1;
    }
    //求叶子结点的个数
    public int getLeafNum(TreeNode root){
        if(root == null)
            return 0;
        if(root.left == null && root.right == null)
            return 1;
        return getLeafNum(root.left)+getLeafNum(root.right);
    }
    //求只有左结点的结点个数
    public int getLeftNodeNum(TreeNode root){
        if(root == null)
            return 0;
        if(!(root.left != null && root.right == null))
            return getLeftNodeNum(root.left)+getLeftNodeNum(root.right);
        return 1;
    }
    //求只有右结点的结点个数
    public int getRightNodeNum(TreeNode root){
        if(root == null)
            return 0;
        if(!(root.left == null && root.right != null))
            return getRightNodeNum(root.left)+getRightNodeNum(root.right);
        return 1;
    }
    //求单结点的结点个数
    public int getSingleNodeNum(TreeNode root){
        if(root == null)
            return 0;
        if(!(root.left == null && root.right != null || root.left != null && root.right == null))
            return getSingleNodeNum(root.left)+getSingleNodeNum(root.right);
        return 1;
    }
    //求双结点的结点个数
    public int getBothNodeNum(TreeNode root){
        if(root == null)
            return 0;
        if(!(root.left != null && root.right != null))
            return getBothNodeNum(root.left)+getBothNodeNum(root.right);
        return getBothNodeNum(root.left)+getBothNodeNum(root.right)+1;
    }
    // 获取第K层节点的个数
    public int getKLevelNodeCount(TreeNode root,int k){
        if(root == null)
            return 0;
        if(k == 1 && root.left == null && root.right == null)
            return 1;
        return getKLevelNodeCount(root.left, k-1) + getKLevelNodeCount(root.right, k-1);
    }
    // 获取二叉树的高度
    public int getHeight(TreeNode root){
        if(root == null)
            return 0;
        if(root.left == null && root.right == null)
            return 1;
        int leftH = getHeight(root.left);
        int rightH = getHeight(root.right);
        return Math.max(leftH, rightH)+1;
    }
    // 检测值为value的元素是否存在
    public TreeNode find(TreeNode root, String val){
        if(root == null)
            return null;
        if(root.val.equals(val))
            return root;
        find(root.left, val);
        find(root.right, val);
        return root;
        //return find(root.left, val) == null && find(root.right, val) == null ? null : root;
    }
    //二叉树前序非递归遍历实现
    public void preOrderNotRecursion(TreeNode root){
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;

        while(cur != null || !stack.isEmpty()){
            while(cur != null){
                System.out.print(cur.val+" ");
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.pop().right;
        }
    }
    //二叉树中序非递归遍历实现
    public void inOrderNotRecursion(TreeNode root){
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while(cur != null || !stack.isEmpty()){
            while(cur != null){
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.pop();
            System.out.print(cur.val+" ");
            cur = cur.right;
        }
    }
    //二叉树后序非递归遍历实现
    public void postOrderNotRecursion(TreeNode root){
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        TreeNode top = null;
        while(cur != null || !stack.isEmpty()){
            while(cur != null){
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode tmp  = stack.peek();
            if(tmp.right == null || tmp.right == top){
                stack.pop();
                top = tmp;
                System.out.print(tmp.val+" ");
            }
            else{
                cur = tmp.right;
            }
        }
    }
    // 二叉树的分层遍历
//    public void levelOrder(TreeNode root){
//        TreeNode cur = root;
//        Queue<TreeNode> queue = new LinkedList<>();
//        queue.offer(cur);
//        while(!queue.isEmpty()){
//            TreeNode tmp = queue.poll();
//            if(tmp.left != null)
//                queue.offer(tmp.left);
//            if(tmp.right != null)
//                queue.offer(tmp.right);
//            System.out.print(tmp.val+" ");
//        }
//    }
    //二叉树的分层遍历
    public void levelOrder(TreeNode root){
        Queue<List<TreeNode>> queue = new LinkedList<>();
        TreeNode cur = root;
        List<TreeNode> curList = new LinkedList<>();
        curList.add(cur);
        queue.add(curList);
        while(!queue.isEmpty()){
            List<TreeNode> tmpList = queue.poll();
            List<TreeNode> tmp2 = new LinkedList<>();
            for(TreeNode top : tmpList){
                if(top.left != null)
                    tmp2.add(top.left);
                if(top.right != null)
                    tmp2.add(top.right);
                System.out.print(top.val+" ");
            }
            if(!tmp2.isEmpty())
                queue.add(tmp2);
        }
    }

}
